package _interview75;

import _object.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 872. 叶子相似的树
 */
public class No872 {
    /**
     * 1. 自顶向下
     */
    public boolean leafSimilar1(TreeNode root1, TreeNode root2) {
        return dfs(root1, new ArrayList<>()).equals(dfs(root2, new ArrayList<>()));
    }

    private List<Integer> dfs(TreeNode node, List<Integer> list) {
        if (node == null) return list;
        dfs(node.left, list);
        dfs(node.right, list);
        if (node.left == null && node.right == null) list.add(node.val);
        return list;
    }

    /**
     * 2. 自底向上
     */
    public boolean leafSimilar2(TreeNode root1, TreeNode root2) {
        return dfs(root1).equals(dfs(root2));
    }

    private List<Integer> dfs(TreeNode node) {
        ArrayList<Integer> list = new ArrayList<>();
        if (node == null) return list;
        list.addAll(dfs(node.left));
        list.addAll(dfs(node.right));
        if (node.left == null && node.right == null) list.add(node.val);
        return list;
    }
}
